class QueueWithMax:
    def __init__(self):
        self.index = 0
        self.data_queue = []
        self.max_queue = []

    def enqueue(self, data):
        indexed_data = (self.index, data)
        while len(self.max_queue) > 0 and self.max_queue[-1][1] < data:
            self.max_queue.pop()
        self.max_queue.append(indexed_data)
        self.data_queue.append(indexed_data)
        self.index += 1

    def dequeue(self):
        indexed_data = self.data_queue.pop(0)
        if self.max_queue[0][0] == indexed_data[0]:
            self.max_queue.pop(0)
        return indexed_data[1]

    def max(self):
        return self.max_queue[0][1]
